package JzOffer.jz60;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Map;

public class Solution02 {
	public int[] topKFrequent(int[] nums, int k) {
		HashMap<Integer, Integer> numToCount = new HashMap<>();
		// 统计频率
		for (Integer num : nums) {
			// 数字为键key,频率为实值value
			numToCount.put(num, numToCount.getOrDefault(num, 0) + 1);
		}

		// 创建用Map中的键值对key-value的实值value进行逆序排序的最小堆
		PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
				new Comparator<Map.Entry<Integer, Integer>>() {
					@Override
					public int compare(Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2) {
						// 大顶堆
						// return -(e1.getValue() - e2.getValue());
						// 小顶堆
						return e1.getValue() - e2.getValue();
					}
				});

		// 遍历映射，添加键值对到最小堆
		for (Map.Entry<Integer, Integer> entry : numToCount.entrySet()) {
			// 保持堆中最多只有K个元素
			if (minHeap.size() < k) {
				minHeap.offer(entry);
			} else if (entry.getValue() > minHeap.peek().getValue()) { // 大于堆顶
				minHeap.poll();
				minHeap.offer(entry);
			}
		}

		int[] res = new int[k];
		int i = 0;
		for (Map.Entry<Integer, Integer> entry : minHeap) {
			res[i++] = entry.getKey();
		}

		return res;
	}
}
